home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1999 March / EnigmA AMIGA RUN 35 (1999)(G.R. Edizioni)(IT)[!][issue 1999-03].iso / earcd / -archivi / -recent2 / gaplib.lha / GAPLib_Beta / doc / text / Tutorial < prev   
Text File  |  1999-01-29  |  9KB  |  264 lines
  1.  
  2. Welcome to the GAP tutorial!
  3.  
  4. This tutorial assumes that GAP is already correctly installed on your system
  5. and that you, the reader, have at least a rudimentary understanding of C.
  6.  
  7.  
  8. Contents:
  9.  
  10. 1 - Overview
  11.  
  12.    1.0    What is GAP?
  13.    1.1    What can I do with GAP?
  14.  
  15. 2 - Step by step tutorial
  16.  
  17.    2.0    Setting up the problem.
  18.    2.1    Designing the individuals.
  19.    2.2    Writing the needed functions.
  20.    2.3    Choosing parameters.
  21.    2.4    Compiling and linking.
  22.    2.5    Running your program.
  23.  
  24. GAP-Lib is (C)1998-1999 Peter Bengtsson, standard disclaimer applies.
  25. ==============================================================================
  26.  
  27. 1.0 What is GAP?
  28.  
  29. GAP is an abbreviation for Genetic Algorithm Programming. It is a code library
  30. for writing programs which implement most any kind of genetic algorithm.
  31.  
  32. GAP-Lib, henceforth called GAP, was written because to provide a simple yet
  33. flexible and powerful base to build such programs upon. The focus has been
  34. on providing the programmer with as much as possible while still allowing her
  35. to change almost any aspect of how the library works.
  36.    As an example one can point to that While GAP is primarily bit-oriented, it
  37. is still written in such a way that one is not restricted to bit
  38. representations. 
  39.  
  40. GAP is not blazingly fast, but it is blazingly good.
  41.  
  42. 1.1 What can I do with GAP?
  43.  
  44. GAP enables you to manage populations, generate statistics and evolve
  45. populations with a minimum of fuss. It can be used for everything from simple
  46. function optimization to empirical studies of GAs themselves. It is however
  47. limited to GA.
  48.  
  49. Some examples of where GAP has been successfully used include:
  50.  
  51.     * Function optimization
  52.     * Evolving rule-based input/action systems.
  53.     * Comparing different representations for problems solved with GA.
  54.  
  55. ==============================================================================
  56.  
  57. 2.0 Setting up the problem.
  58.  
  59. The objective of this tutorial will be to implement a genetic algorithm based
  60. program to optimize the function f(x)=x+sin(32x) in the range x=[0,¶] for the
  61. highest value of f(x). The actual source presented in this tutorial is also
  62. included as a separate file.
  63.  
  64. To accomplish our objective, we will need to set up a fitness function, design
  65. a template for individuals and implement this.
  66.  
  67. 2.1 Designing the individuals.
  68.  
  69. In this case we will simply model the individuals as integers and let this
  70. integer represent a fraction of the range from 0 to ¶ with 0 meaning 0 and
  71. the maximum value of the integer representing ¶.
  72.  
  73. In code this would look something like:
  74.  
  75. struct Polyphant {
  76.    unsigned long value;
  77. };
  78.  
  79. If one wants to, one could omit the struct declaration in this case. But I
  80. personally find it neater to keep it as to show that the individuals are
  81. distinct entities and not just a primitive datatype.
  82.  
  83. 2.2 Writing the needed functions.
  84.  
  85. For this program, only two functions are actually needed. A fitness function
  86. and a main function. For those of you not familiar with C, main is the
  87. starting point of any program - and the program does need somewhere to start.
  88. It is however desirable to have one more function, namely one to initialize
  89. the individuals when creating the population (In reality we could use the
  90. built-in random-initialization function for this.).
  91.  
  92. The main function of this program would look something like this :
  93.  
  94. int main(void)
  95. {
  96. int i;
  97. struct Population *Pop;
  98. struct Polyphant *Individual;
  99. struct TagItem EvolveTags[]={
  100.    {EVL_Evaluator,fitfunc},
  101.    {TAG_DONE,0L}
  102. };
  103. struct TagItem CreateTags[]={
  104.    {POP_Init,init},
  105.    {TAG_DONE,0L}
  106. };
  107.  
  108. EnterGAP(1);
  109.  
  110. Pop = CreatePopulation(20,sizeof(struct Polyphant),CreateTags);
  111.  
  112. for(i=0;i!=25;i++) {
  113.    Pop = Evolve(Pop,EvolveTags);
  114.    printf("Generation %d: Max = %lf\n",i+1,Pop->Stat.MaxFitness);
  115. }
  116.  
  117. Individual = Pop->Stat.Max;
  118.  
  119. printf("After %d generations:\n",i);
  120. printf("Best value = %lf.\n",Pop->Stat.MaxFitness);
  121. printf("For f(%lf).\n",IRange(Individual->value,0,PI));
  122.  
  123. DeletePopulation(Pop);
  124.  
  125. return(0);
  126. }
  127.  
  128. And the other two functions, the init function and the fitness function could
  129. look something like this:
  130.  
  131. void init(struct Polyphant *Polly)
  132. {
  133. /* Rnd() only returns values between 0 and max 2147483646 (30 bits) */
  134. Polly->value = Rnd(0x7ffffffe)^(Rnd(0x7ffffffe)<<2);
  135. }
  136.  
  137. double fitfunc(struct Polyphant *Polly)
  138. {
  139. double x;
  140. x = IRange(Polly->value,0,PI);
  141. return(x+sin(32*x));
  142. }
  143.  
  144. 2.3 Choosing parameters.
  145.  
  146. Choosing the right parameters for your GA can be very important for its
  147. performance. In GAP, most of the parameters can either be specified to the
  148. Evolve() function or should be built-in into the fitness, crossover and
  149. mutation functions. One other parameter however which is not specified in
  150. either of those places is the size of the population.
  151.  
  152. In the above code, the size of the population was arbitrarily set to 20
  153. individuals. You might wish to experiment with this value to see if the
  154. behaviour of the GA changes.
  155.  
  156. Regarding parameters built into the fitness function and the representation
  157. of the individuals themselves, we have an example of this in the fact that
  158. we have let an integer represent a real number between 0 and ¶.
  159.  
  160. Lastly, we have the parameters one can specify to the Evolve() function.
  161. Evolve() takes two formal parameters, one which is the population and one
  162. which is a list of parameters on the form {{Parameter,Value},{},...}.
  163. Of the parameters in this list only two are necessary, EVL_Evaluator - which
  164. is used to specify the fitness function to use, and TAG_DONE which denotes
  165. the end of the parameter list (Taglist).
  166.    Other tags (parameters) in the list which you might want to try for this
  167. problem are EVL_Select and EVL_Elite.
  168.  
  169. 2.4 Compiling and linking.
  170.  
  171. If you have now written your main, fitness and initialization functions, you
  172. need only write a little more code and you will be ready to test your program.
  173.  
  174. The prototypes for Evolve(), CreatePopulation() etc. are in the file GAP.h
  175. so in the beginning of your program you should include <GAP.h> for these.
  176.  
  177. You should also have prototypes for your fitness and initialization functions
  178. in addition to having defined the type for the individuals. So the beginning
  179. of your program could look something like this:
  180.  
  181. #include <stdio.h>
  182. #include <GAP.h>
  183. #include <math.h>
  184.  
  185. struct Polyphant {
  186.    unsigned long value;
  187. };
  188.  
  189. #ifndef    PI
  190. #define    PI 3.14159265359
  191. #endif
  192.  
  193. void init(struct Polyphant *);
  194. double fitfunc(struct Polyphant *);
  195. ...
  196. ...
  197.  
  198. Now if you have finished writing the program, all you need to do is to compile
  199. it before you can test it. Assuming you are using an ISO-C compliant C
  200. compiler under some UNIX flavour and have named your source file 'tutorial.c' :
  201.  
  202. cc tutorial.c -o tutorial -lgap -lm
  203.  
  204. The compiler will probably complain about the line containing 
  205. {EVL_Evaluator,fitfunc} with a message like "initialization makes integer from
  206. pointer without a cast". If you want to you can perform the cast and rewrite
  207. it like {EVL_Evaluator,(IPTR)fitfunc}.
  208.  
  209. Assuming no errors occurred all you have to do now is to test your program,
  210. otherwise you now have the task of correcting those errors at hand. If you
  211. are unfamiliar with C, you might want to have a more experienced C-programmer
  212. to have a look at the code.
  213.  
  214. 2.5 Running your program.
  215.  
  216. Now, finally, you have written your first program using GAP. A the prompt
  217. (assuming you work in a shell environment) type :
  218.  
  219. tutorial
  220.  
  221. And press enter (assuming you named the program 'tutorial').
  222.  
  223. The program should generate some output like this:
  224.  
  225. Generation 1: Max = 3.642083
  226. Generation 2: Max = 3.664751
  227. Generation 3: Max = 3.664751
  228. Generation 4: Max = 3.667555
  229. Generation 5: Max = 3.690620
  230. Generation 6: Max = 3.690894
  231. Generation 7: Max = 3.690893
  232. Generation 8: Max = 3.690894
  233. Generation 9: Max = 3.690893
  234. Generation 10: Max = 3.690893
  235. Generation 11: Max = 3.690894
  236. Generation 12: Max = 3.690915
  237. Generation 13: Max = 3.690916
  238. Generation 14: Max = 3.690915
  239. Generation 15: Max = 3.690916
  240. Generation 16: Max = 3.690916
  241. Generation 17: Max = 3.690916
  242. Generation 18: Max = 3.690916
  243. Generation 19: Max = 3.690916
  244. Generation 20: Max = 3.690916
  245. Generation 21: Max = 3.690916
  246. Generation 22: Max = 3.690916
  247. Generation 23: Max = 3.690916
  248. Generation 24: Max = 3.690916
  249. Generation 25: Max = 3.690916
  250. After 25 generations:
  251. Best value = 3.690916.
  252. For f(2.784364).
  253.  
  254. One can readily see that this is far from an optimal value (The exact best
  255. value is 1+61*¶/64 (approximately 3.99) for 61*¶/64) and I leave it as an
  256. exercise to improve the GA by choosing better parameters for this problem -
  257. which I will again take the opportunity to stress is very important.
  258.  
  259. (Hint: Add more items to the Evolve TagList.)
  260.  
  261. And this is the end of the tutorial, happy hacking!
  262.  
  263.     -Peter Bengtsson (29/1-1999)
  264.